/*
 *  Copyright (C) 2010 Martin Haulrich <mwh.isv@cbs.dk>
 *
 *  This file is part of the MatrixParser package.
 *
 *  The MatrixParser program is free software: you can redistribute it and/or modify
 *  it under the terms of the GNU Lesser General Public License as published by
 *  the Free Software Foundation, either version 3 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU Lesser General Public License for more details.
 *
 *  You should have received a copy of the GNU Lesser General Public License
 *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */
package org.osdtsystem.matrixparser.learners;

import org.osdtsystem.matrixparser.parsers.ParsingModel;
import org.osdtsystem.matrixparser.features.WeightVector;
import java.util.List;
import java.util.Map.Entry;
import org.osdtsystem.matrixparser.features.DenseFeatureVector;
import org.osdtsystem.matrixparser.features.Feature;
import org.osdtsystem.matrixparser.features.FeatureVector;
import org.osdtsystem.matrixparser.features.FeatureVectorUtils;

/**
 * 'upd' argument in update method should be:
 *    number of iteration * number of instances - (number of instances * (current iteration - 1) + (current instance + 1) + 1)
 *
 * @author Martin Haulrich
 */
public class MIRALearner extends AbstractLearnerK {
    ParsingModel model;
    DenseFeatureVector weights;
    DenseFeatureVector sumWeights;
    int updates;
    final boolean average;

    public MIRALearner(ParsingModel model, int paramSize) {
        this(model, paramSize, true);
    }

    public MIRALearner(ParsingModel model, int paramSize, boolean average) {
        this.model = model;
        this.average = average;
        weights = model.weights();
        sumWeights = new DenseFeatureVector(paramSize);
        updates = 0;
    }

    public MIRALearner(ParsingModel model) {
        this(model, 1);
    }

    public ParsingModel model() {
        return model;
    }
    
    @Override
    public WeightVector getWeightVector() {
        return weights;
    }

    @Override
    public void averageWeights() {
        double avVal = (double) updates;
        for (int i = 0; i < weights.size(); i++) {
            weights.setValue(i, sumWeights.getValue(i) / avVal);
        }
//        for (Feature f : sumWeights.allEntries()) {
//            weights.setWeight(f, sumWeights.getWeight(f) / avVal);
//        }
    }

    @Override
    public void updateK(FeatureVector goldVector, List<FeatureVector> systemVectors, Scorer scorer,
            List<Double> loss, double upd) {
        //System.err.println("\nUPDATE: " + upd);
        updates++;

        int K = systemVectors.size();

        FeatureVector[] distVectors = new FeatureVector[K];
        double[] tLoss = new double[K];

        double goldScore = scorer.getScore(weights, goldVector);

        for (int k = 0; k < K; k++) {

            double score = scorer.getScore(weights, systemVectors.get(k));
            double scoreDiff = goldScore - score;

            tLoss[k] = loss.get(k) - scoreDiff;

            distVectors[k] = FeatureVectorUtils.distance(goldVector, systemVectors.get(k));
        }

        double[] alpha = hildreth(distVectors, tLoss);

        for (int k = 0; k < K; k++) {
            updateWeights(upd, alpha[k], distVectors[k]);
        }

    }

    private void updateWeights(double upd, double alpha, FeatureVector fv) {

        for (Entry<Feature,Double> entry : fv) {
            Feature f = entry.getKey();
            Double fvalue = entry.getValue();

            Double w = weights.getValue(f);
            if (w == null) {
                w = 0.0;
            }

            weights.setValue(f, w + alpha * fvalue);

            Double sW = sumWeights.getValue(f);
            if (sW == null) {
                sW = 0.0;
            }
            sumWeights.setValue(f, sW + upd * alpha * fvalue);
        }
    }

    /**
     *  * This method is almost a exact copy of the chuLiuEdmonds algorithm from the MSTParser-project
     *   http://sourceforge.net/projects/mstparser/
     */
    private double[] hildreth(FeatureVector[] a, double[] b) {

        int i;
        int max_iter = 10000;
        double eps = 0.00000001;
        double zero = 0.000000000001;

        double[] alpha = new double[b.length];

        double[] F = new double[b.length];
        double[] kkt = new double[b.length];
        double max_kkt = Double.NEGATIVE_INFINITY;

        int K = a.length;

        double[][] A = new double[K][K];
        boolean[] is_computed = new boolean[K];
        for (i = 0; i < K; i++) {
//            A[i][i] = a[i].dotProduct(a[i]);
            A[i][i] = FeatureVectorUtils.dotProduct(a[i], a[i]);
            is_computed[i] = false;
        }

        int max_kkt_i = -1;

        for (i = 0; i < F.length; i++) {
            F[i] = b[i];
            kkt[i] = F[i];
            if (kkt[i] > max_kkt) {
                max_kkt = kkt[i];
                max_kkt_i = i;
            }
        }

        int iter = 0;
        double diff_alpha;
        double try_alpha;
        double add_alpha;

        while (max_kkt >= eps && iter < max_iter) {

            diff_alpha = A[max_kkt_i][max_kkt_i] <= zero ? 0.0 : F[max_kkt_i] / A[max_kkt_i][max_kkt_i];
            try_alpha = alpha[max_kkt_i] + diff_alpha;
            add_alpha = 0.0;

            if (try_alpha < 0.0) {
                add_alpha = -1.0 * alpha[max_kkt_i];
            } else {
                add_alpha = diff_alpha;
            }

            alpha[max_kkt_i] = alpha[max_kkt_i] + add_alpha;

            if (!is_computed[max_kkt_i]) {
                for (i = 0; i < K; i++) {
//                    A[i][max_kkt_i] = a[i].dotProduct(a[max_kkt_i]); // for version 1
                    A[i][max_kkt_i] = FeatureVectorUtils.dotProduct(a[i], a[max_kkt_i]);
                    is_computed[max_kkt_i] = true;
                }
            }

            for (i = 0; i < F.length; i++) {
                F[i] -= add_alpha * A[i][max_kkt_i];
                kkt[i] = F[i];
                if (alpha[i] > zero) {
                    kkt[i] = Math.abs(F[i]);
                }
            }

            max_kkt = Double.NEGATIVE_INFINITY;
            max_kkt_i = -1;
            for (i = 0; i < F.length; i++) {
                if (kkt[i] > max_kkt) {
                    max_kkt = kkt[i];
                    max_kkt_i = i;
                }
            }
            iter++;
        }
        return alpha;
    }

}
